
// 给定一个字符串，请设计算法找出其最长的不含重复字符的子字符串，并计算该字符串长度。

var lengthOfLongestSubstring: (s: string) => number = function (s) {
    //初始化哈希表、头指针、尾指针
    let hashMap = new Map<string, number>();
    let head: number = 0;
    let res: number = 0;
    //遍历字符串
    for (let tail: number = 0; tail < s.length; tail++) {
        // 判断哈希表中是否存在当前字符
        if (hashMap.has(s[tail])) {
            // 这里注意！要取head指针和哈希表值中的大值，否则头指针可能会往左移
            head = Math.max(<number>hashMap.get(s[tail]) + 1, head);
        }
        // 更新hashMap与res
        hashMap.set(s[tail], tail);
        res = Math.max(res, tail - head + 1);
    }
    return res;
};

        // 首先，因为题目中要求必须是子串的长度，意味着子串内的字符在原字符串中一定是连续的
        // 看到这里连续的要求我们就可以想到滚动窗口算法了
        // 我们把最长的子串看作是原字符串的一个滑动窗口，我们维护这个窗口使得窗口内不能出现重复的元素
        // 同时动态的更新长度的最大值
        // 具体写法就是我们先初始化头尾指针 head，tail
        // 循环字符串，让tail指针不断右移，判断 tail 指向的元素是否在的窗口内
        // 如果不在窗口内则将该元素加入窗口，同时更新窗口长度最大值，tail 指针继续右移；
        // 如果窗口中存在该元素，则将 head 指针右移，保证窗口中不包含该重复元素。
        // 在head指针的处理上有一个优化的方法，就是使用哈希表
        // 我们令哈希表的key值为单字符，value值为它对应的索引位置
        // 使用哈希表记录每个窗口字符的索引，如果尾指针指向的元素重复，则将头指针直接移动到窗口中该重复元素的右侧。
        // 每一个轮次我们要做的事情也很简单，就是右移tail指针，用哈希表判别，如果重复那么就挪动head指针
        // 之后维护子串长度与哈希表
        // 注意一下头指针在窗口滑动时是可能左移的，例如“abba”中遇到第二个“a”时，
        // 头指针就可能会左移导致结果错误....所以在这里就要取最大值